package dp;

public class _09_416_分割等和子集_滚动数组 {
    public static boolean canPartition(int[] nums) {
    	// 题目中 1 <= nums.length <= 200
    	// 但是dp用到的大小是所有元素和的一半，而元素的大小：1 <= nums[i] <= 100
    	// 因此 N = (200*100)/2 + 10
    	int N = 10010;
    	int sum = 0;
    	int dp[] = new int[N];
    	for(int i = 0; i < nums.length; i++) {
    		sum += nums[i];
    	}
    	if(sum % 2 == 1) {
    		return false;
    	}
    	int mid = sum/2;
    	
    	for(int i = 1; i <= nums.length; i++) {
    		// i是元素，j是和值，如果nums[i-1]比和值还大，说明该元素根本用不到
    		for(int j = mid; j >= nums[i-1]; j--) {
    			dp[j] = Math.max(dp[j], dp[j-nums[i-1]] + nums[i-1]);
    			if(dp[j] == mid) {
    				return true;
    			}
    		}
    	}
    	
    	return false;
    }
    
    public static void main(String[] args) {
    	int[] nums = {100,100,100,100,100};
    	System.out.println(canPartition(nums));
	}
}
